/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        76.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 13:16
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给你一个字符串 s 、一个字符串 t 。
// 返回 s 中涵盖 t 所有字符的最小子串。
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
#include "../header.h"

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> needs, window;
        for (char c : t)
            needs[c]++;
        int left = 0, right = 0;
        int valid = 0;

        int start = 0, len = INT_MAX;
        while (right < s.size()){
            char c = s[right];
            right++;
            if (needs.count(c)) {
                window[c]++;
                if (window[c] == needs[c])
                    valid++;
            }
            while (valid == needs.size()){
                if (right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s[left];
                left++;
                if (needs.count(d)){
                    if (window[d] == needs[d])
                        valid--;
                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "":s.substr(start,len);
    }
};
